#include "StdAfx.h"
#include "Intelligence.h"

#include <ctime>
#include <cstdlib>
#include <cmath>

#include "UniversalFunctionsSet.h"

static const int16_t INFLUENCE_CENTER_VALUE = 3360;
static const int8_t INFLUENCE_MAX_DISTANCE = 8;
static const float MAX_UCB_VALUE = (float)100000.0;

CIntelligence::CIntelligence(int8_t lineCount): m_LineCount(lineCount)
{
	TRACE("lineCount = %d\n", lineCount);
	m_MaxPlayCount = 1000;
}


void CIntelligence::Init(void)
{
	m_TranspositionTable.Init();

	GenerateRandomBoardElementValue();
}


CIntelligence::~CIntelligence(void)
{
}


/*void CIntelligence::EvaluateSituation(void)
{
	for (size_t i=0; i<m_SituationBoard.size(); i++) {

	}
}*/


void CIntelligence::Think(const CGoBoardWithCommonProcess &givenPosition,
	SLocationOnGoBoard *pFoolishMove)
{
	CGoBoardWithCommonProcess trialBoard(m_LineCount);
	trialBoard.Copy(givenPosition);
	UCTAlgorithm(trialBoard, pFoolishMove);
}


inline int CIntelligence::LocationToScript(const SLocationOnGoBoard &location) const
{
	return location.x + location.y * m_LineCount;
}


inline int8_t CIntelligence::ScriptToX(int script) const
{
	return script % m_LineCount;
}


inline int8_t CIntelligence::ScriptToY(int script) const
{
	return script / m_LineCount;
}


/*void CIntelligence::EvaluateOnePieceInfluence(int script, TPlayerColor color)
{
	int8_t x = ScriptToX(script);
	int8_t y = ScriptToY(script);
	int8_t scriptAdd[4][2] = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}};
	const int8_t bound = 2 * INFLUENCE_MAX_DISTANCE + 1;
	//int8_t distanceBoard[bound];
	for (int8_t distance=1; distance<=INFLUENCE_MAX_DISTANCE; distance++) {
		for (int i=0; i<4; i++) {

		}
	}
}*/


void CIntelligence::GenerateRandomMove(CGoBoardWithCommonProcess *pGoBoardWithCommonProcess) const
{
	int lineCount = pGoBoardWithCommonProcess->m_GoBoard.GetLineCount();
	int square = lineCount * lineCount;
	int availableCount = square - pGoBoardWithCommonProcess->m_PiecesNumber[BLACK_COLOR] -
		pGoBoardWithCommonProcess->m_PiecesNumber[WHITE_COLOR];
	srand((unsigned)time(NULL));
	int randomScript = rand() % availableCount;
	int mark = 0;
	for (int i=0; i< 2 * square; i++) {
		int script = i % square;
		if (pGoBoardWithCommonProcess->m_GoBoard.m_OneColorBoard[BLACK_COLOR][script] == EMPTY_ON_POINT &&
			pGoBoardWithCommonProcess->m_GoBoard.m_OneColorBoard[WHITE_COLOR][script] == EMPTY_ON_POINT) {
				if (mark == randomScript) {
					SLocationOnGoBoard pointToMove;
					pointToMove.x = ScriptToX(script);
					pointToMove.y = ScriptToY(script);

					if (WillFillInTrueEye(*pGoBoardWithCommonProcess, pointToMove)) continue;

					if (pGoBoardWithCommonProcess->Move(pointToMove)) return;

				} else /*if (mark < randomScript)*/ {
					mark++;
					continue;
				}
		}
	}
	pGoBoardWithCommonProcess->Pass();
}


bool CIntelligence::WillFillInTrueEye(const CGoBoardWithCommonProcess &goBoardWithCommonProcess,
	const SLocationOnGoBoard &pointToMove) const
{
	ASSERT(goBoardWithCommonProcess.m_GoBoard.GetPointStatus(BLACK_COLOR, pointToMove) == EMPTY_ON_POINT &&
		goBoardWithCommonProcess.m_GoBoard.GetPointStatus(WHITE_COLOR, pointToMove) == EMPTY_ON_POINT);

	TPlayerColor colorToMove = goBoardWithCommonProcess.m_PlayerToMove;
	int scriptAdd[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
	int invalidCount = 0;
	for (int i=0; i<4; i++) {
		SLocationOnGoBoard sideLocation;
		sideLocation.x = pointToMove.x + scriptAdd[i][0];
		sideLocation.y = pointToMove.y + scriptAdd[i][1];
		if (goBoardWithCommonProcess.LocationIsValid(sideLocation)) {
			if (goBoardWithCommonProcess.m_GoBoard.GetPointStatus(colorToMove, sideLocation) ==
				EMPTY_ON_POINT) {
				return false;
			}
		} else {
			invalidCount++;
		}
	}

	int cornerScriptAdd[4][2] = {{1, 1}, {1, -1}, {-1, -1}, {-1, 1}};
	int piecesCount = 0;
	for (int i=0; i<4; i++) {
		SLocationOnGoBoard sideLocation;
		sideLocation.x = pointToMove.x + cornerScriptAdd[i][0];
		sideLocation.y = pointToMove.y + cornerScriptAdd[i][1];

		if (!goBoardWithCommonProcess.LocationIsValid(sideLocation)) continue;

		if (goBoardWithCommonProcess.m_GoBoard.GetPointStatus(colorToMove, sideLocation) ==
			PIECE_ON_POINT) {
			piecesCount++;
		}
	}

	ASSERT(invalidCount == 0 || invalidCount == 1 || invalidCount == 2);

	int trueEyeLevel = ~invalidCount & 3;
	if (piecesCount >= trueEyeLevel) {
		return true;
	} else {
		return false;
	}
}
 

void CIntelligence::RandomPlay(CGoBoardWithCommonProcess *pGoBoardWithCommonProcess,
	SGameResult *pResult) const
{
	int count = 0;
	while (!pGoBoardWithCommonProcess->IsGameEnd() && ++count < 200) {
		GenerateRandomMove(pGoBoardWithCommonProcess);
		//pGoBoardWithCommonProcess->m_GoBoard.Print();
	}
	TLocationVector blackAera;
	TLocationVector whiteArea;
	if (count >= 200) {
		pResult->blackScore = 40;
		pResult->whiteScore = 40;
	} else {
		pGoBoardWithCommonProcess->Shuzi(pGoBoardWithCommonProcess->m_GoBoard, &blackAera, &whiteArea, pResult);
	}
}


int32_t CIntelligence::GetZobristHash(const CGoBoardWithCommonProcess &givenPosition) const
{
	int32_t key = 0;
	int square = m_LineCount * m_LineCount;
	for (int i=0; i<square; i++) {
		if (givenPosition.m_GoBoard.m_OneColorBoard[BLACK_COLOR][i] == PIECE_ON_POINT) {
			key ^= m_boardElementValue.pointValue[i][0];
		} else if (givenPosition.m_GoBoard.m_OneColorBoard[WHITE_COLOR][i] == PIECE_ON_POINT) {
			key ^= m_boardElementValue.pointValue[i][1];
		} else {
			key ^= m_boardElementValue.pointValue[i][2];
		}
	}
	if (givenPosition.m_JieLocaton.x == NONE_LOCATION) {
		key ^= m_boardElementValue.noJieValue;
	} else {
		key ^= m_boardElementValue.jieValue[givenPosition.m_JieLocaton.x +
			m_LineCount *givenPosition.m_JieLocaton.y];
	}
	if (givenPosition.m_PlayerToMove == BLACK_COLOR) {
		key ^= m_boardElementValue.colorToMoveValue[0];
	} else {
		key ^= m_boardElementValue.colorToMoveValue[1];
	}
	return key;
}


void CIntelligence::GenerateRandomBoardElementValue(void)
{
	srand((unsigned)time(NULL));
	int square = m_LineCount * m_LineCount;
	for (int i=0; i<square; i++) {
		m_boardElementValue.pointValue[i][0] = GetPositive32BitRandomInteger();
		m_boardElementValue.pointValue[i][1] = GetPositive32BitRandomInteger();
		m_boardElementValue.pointValue[i][2] = GetPositive32BitRandomInteger();
		m_boardElementValue.jieValue[i] = GetPositive32BitRandomInteger();
	}
	m_boardElementValue.noJieValue = GetPositive32BitRandomInteger();
	m_boardElementValue.colorToMoveValue[0] = GetPositive32BitRandomInteger();
	m_boardElementValue.colorToMoveValue[1] = GetPositive32BitRandomInteger();
}


int32_t CIntelligence::GetPositive32BitRandomInteger(void) const
{
	int32_t add = rand() << 16;
	return add + rand();
}


void CIntelligence::UCTAlgorithm(const CGoBoardWithCommonProcess &rootPosition,
	SLocationOnGoBoard *pBestMove)
{
	CString name("\\log.txt");
	CreatLog(name);
	CString str("Computer to move\r\n");
	FileLog(rootPosition,str,name);

	CBoardStack boardStack(m_LineCount);
	boardStack.Init();

	//int playCount = 0;
	boardStack.Push(rootPosition);
	int playCount = 0;
	while (playCount < m_MaxPlayCount) {
		//playCount++;
		TRACE("***********begin total recycle***************\n");
		CGoBoardWithCommonProcess father(m_LineCount);

		ASSERT(boardStack.GetElementCount() > 0);

		boardStack.GetTop(&father);
		int32_t key = GetZobristHash(father);
		SPositionInformation info;
		if(m_TranspositionTable.Search(key, &info)) {
			if (info.isCompleted) {
				break;
			}
		}

		CGoBoardWithCommonProcess son(m_LineCount);
		FileLog(father, CString("max ucb value\r\n"), name);
		if (GetMaxUCBSonNode(father, &son)) {
			int32_t sonKey = GetZobristHash(son);
			SPositionInformation sonInfo;

			if (m_TranspositionTable.Search(sonKey, &sonInfo)) {
				CString str("pushStack\r\n");
				FileLog(son, str, name);
				boardStack.Push(son);
				if (boardStack.GetElementCount() > 200) {
					boardStack.Clear();
					boardStack.Push(rootPosition);
				}
			} else {
				CGoBoardWithCommonProcess trialBoard(m_LineCount);
				trialBoard.Copy(son);
				SGameResult gameResult;

				CString str("randombegin\r\n");
				FileLog(son, str, name);

				RandomPlay(&trialBoard, &gameResult);
				playCount++;
				boardStack.Push(son);
				TRACE("************************UpdateInterest***************************\n");
				Log(CString("Random play finished\r\n"), name);
				UpdateInterest(&boardStack, gameResult);
				Log(CString("update interest finished\r\n"), name);
			}
		} else {
			SPositionInformation info;
			int32_t key = GetZobristHash(father);
			m_TranspositionTable.Search(key, &info);
			info.isCompleted = true;
			m_TranspositionTable.Update(key, info);
			boardStack.Pop();
		}
	}
	TRACE("******************MaxInterestMove****************************\n");
	Log(CString("max interest\r\n"), name);
	GetMaxInterestMove(rootPosition, pBestMove);
}


float CIntelligence::GetUCBValue(int32_t key, int n) const
{
	SPositionInformation info;
	m_TranspositionTable.Search(key, &info);
	//float UCBValue = info.averageInterest + sqrt(log((float)n) / info.reachCount / 4);
	float UCBValue = info.averageInterest + sqrt(log((float)n) / info.reachCount / 4);
	return UCBValue;
}


bool CIntelligence::GetMaxUCBSonNode(const CGoBoardWithCommonProcess &father,
	CGoBoardWithCommonProcess *pSon) const
{
	int square = m_LineCount * m_LineCount;
	int32_t keyArray[361];
	int scriptArray[361];
	int keyArrayLength = 0;
	int n = 0;
	bool isGameEnd = true;
	for (int i=0; i<square; i++) {
		SLocationOnGoBoard pointToMove;
		pointToMove.x = ScriptToX(i);
		pointToMove.y = ScriptToY(i);
		if (father.m_GoBoard.GetPointStatus(BLACK_COLOR, pointToMove) == PIECE_ON_POINT) continue;
		if (father.m_GoBoard.GetPointStatus(WHITE_COLOR, pointToMove) == PIECE_ON_POINT) continue;
		if (WillFillInTrueEye(father, pointToMove)) continue;
		CGoBoardWithCommonProcess trialBoard(m_LineCount);
		trialBoard.Copy(father);
		if (trialBoard.Move(pointToMove)) {
			keyArrayLength++;
			scriptArray[keyArrayLength - 1] = i;
			keyArray[keyArrayLength - 1] = GetZobristHash(trialBoard);
			SPositionInformation info;
			if (m_TranspositionTable.Search(keyArray[keyArrayLength - 1], &info)) {
				n += info.reachCount;
				if (!info.isCompleted) isGameEnd = false;
			} else {
				pSon->Copy(trialBoard);
				return true;
			}
		}
	}
	if (isGameEnd) {
		return false;
	}else {
		float maxUCB = -1000.0;
		SLocationOnGoBoard maxUCBMove;

		for (int i=0; i<keyArrayLength; i++) {
			float UCBValue = GetUCBValue(keyArray[i], n);
			if (UCBValue > maxUCB) {
				maxUCB = UCBValue;
				maxUCBMove.x = ScriptToX(scriptArray[i]);
				maxUCBMove.y = ScriptToY(scriptArray[i]);
			}
		}

		pSon->Copy(father);
		pSon->Move(maxUCBMove);
		return true;
	}
}


void CIntelligence::UpdateInterest(CBoardStack *pBoardStack, const SGameResult &result)
{
	CGoBoardWithCommonProcess top(m_LineCount);

	ASSERT(pBoardStack->GetElementCount() > 0);

	pBoardStack->GetTop(&top);
	pBoardStack->Pop();
	int32_t key = GetZobristHash(top);
	float symbol;
	if (top.m_PlayerToMove == WHITE_COLOR) {
		symbol = result.blackScore / (float)81.0;
	} else {
		symbol = result.whiteScore / (float)81.0;
	}
	SPositionInformation info;
	info.reachCount = 1;
	info.averageInterest = (float)symbol;
	info.isCompleted = false;
	m_TranspositionTable.Insert(key, info);

	while (pBoardStack->GetElementCount() > 1) {
		symbol = 1 - symbol;
		CGoBoardWithCommonProcess node(m_LineCount);
		pBoardStack->GetTop(&node);
		pBoardStack->Pop();
		int32_t key = GetZobristHash(node);
		SPositionInformation oldInfo;
		bool searched = m_TranspositionTable.Search(key, &oldInfo);
		SPositionInformation newInfo;
		newInfo.reachCount = oldInfo.reachCount + 1;
		newInfo.averageInterest = (oldInfo.averageInterest * oldInfo.reachCount + symbol) / newInfo.reachCount;
		newInfo.isCompleted = false;
		m_TranspositionTable.Update(key, newInfo);
	}
}


void CIntelligence::GetMaxInterestMove(const CGoBoardWithCommonProcess &givenBoard,
	SLocationOnGoBoard *pBestMove) const
{
	float maxInterest = -100.0;
	SLocationOnGoBoard bestMove;
	int square = m_LineCount * m_LineCount;
	for (int i=0; i<square; i++) {
		CGoBoardWithCommonProcess trialBoard(m_LineCount);
		trialBoard.Copy(givenBoard);
		SLocationOnGoBoard point;
		point.x = ScriptToX(i);
		point.y = ScriptToY(i);
		if (trialBoard.m_GoBoard.GetPointStatus(BLACK_COLOR, point) == PIECE_ON_POINT) continue;
		if (trialBoard.m_GoBoard.GetPointStatus(WHITE_COLOR, point) == PIECE_ON_POINT) continue;
		if (WillFillInTrueEye(trialBoard, point)) continue;
		if (trialBoard.Move(point)) {
			int32_t key = GetZobristHash(trialBoard);
			SPositionInformation info;
			m_TranspositionTable.Search(key, &info);
			TRACE("%d  ",i);
			TRACE("%d  ", info.reachCount);
			TRACE("interest = %f\n",info.averageInterest);
			if (info.averageInterest > maxInterest) {
				maxInterest = info.averageInterest;
				bestMove.x = ScriptToX(i);
				bestMove.y = ScriptToY(i);
				TRACE("maxinterest = %f\n", maxInterest);
			}
		}
	}
	*pBestMove = bestMove;
}


void CIntelligence::FileLog(const CGoBoardWithCommonProcess &goBoard, const CString &info, const CString &name) const
{
	CString path = uf::GetCurrentPath();
	path.Append(name);
	CStdioFile file(path, CFile::modeWrite);
	file.SeekToEnd();
	file.WriteString(info);
	int square = m_LineCount * m_LineCount;
	for (int i=0; i<square; i++) {
		CString buffer;
		if (goBoard.m_GoBoard.m_OneColorBoard[BLACK_COLOR][i] == PIECE_ON_POINT) {
			buffer = CString("@");
		} else if (goBoard.m_GoBoard.m_OneColorBoard[WHITE_COLOR][i] == PIECE_ON_POINT) {
			buffer = CString("o");
		} else {
			buffer = CString("+");
		}
		file.WriteString(buffer);
		if (i % 9 == 8) {
			buffer = CString("\r\n");
			file.WriteString(buffer);
		}
	}
	file.WriteString((LPCTSTR)("\n"));
	file.WriteString((LPCTSTR)("\n"));
	file.Close();
}


void CIntelligence::CreatLog(const CString &name) const
{
	CString path = uf::GetCurrentPath();
	path.Append(name);
	CStdioFile file(path, CFile::modeCreate);
	file.Close();
}


void CIntelligence::Log(const CString &str, const CString &name) const
{
	CString path = uf::GetCurrentPath();
	path.Append(name);
	CStdioFile file(path, CFile::modeWrite);
	file.SeekToEnd();
	file.WriteString(str);
}